/*
 * Algorithem.cpp
 *
 *  Created on: Dec 12, 2009
 *      Author: ssperetz
 */

#include "Algorithem.h"
#include <math.h>
#include <list>

//TODO for testing ,to delete
#include <iostream>

using namespace std;

int Algorithem::selectedSquare = -1;
//double Algorithem::maxHeuristic;
//double Algorithem::minHeuristic;
int Algorithem::numOfSticks;
double Algorithem::coefficientProbabilty;
Heuristic* Algorithem::curHeuristic;
int Algorithem::counter = 0;
int Algorithem::counterIteritive = 0;


int Algorithem::curBestDepth;

//TODO to delete
bool Algorithem::flag = false;
int Algorithem::curException = 0;

int Algorithem::startExpectiMax(SmartSenetBoard& smartSenetBoard,
		GameTimer& my_timer, Heuristic* h) {

	curHeuristic = h;
	Definitions::PlayerColor playerColor = smartSenetBoard.getCurPlayerColor();
	numOfSticks = smartSenetBoard.m_num_sticks;
	coefficientProbabilty = pow(0.5, numOfSticks);
	//	setMaxMinHeuristics(smartSenetBoard);

	try {
		expectimax(smartSenetBoard, playerColor, false, 6, true, my_timer);
	} catch (int x) {
		if (x == 1) {
			//TODO remove this before submission
			//printf(
			//		"*******************SHITTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtt I'm out of time***************************************************\n");
		}
	}

	// maybe return Move instead of int
	return selectedSquare;

}

double Algorithem::expectimax(SmartSenetBoard& curBoard,
		const Definitions::PlayerColor myColor, bool isChanceState, int depth,
		bool isFirst, GameTimer& my_timer) {

	vector<SenetMove> nextLegalMoves;
	SenetMove nextMove;
	double curMax, curMin, value;
	int posBefore, posAfter;
	Definitions::PlayerColor curColor;
	int numOnSticks;
	SenetChanceState senetChanceState;
	bool isPeaceOnReBirthPlace = false;

	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK)
			|| (curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE)
			|| (depth == 0)) {
		return heuristic(curBoard, myColor); // should return heuristic here
	}

	curColor = curBoard.getCurPlayerColor();
	numOnSticks = curBoard.getSticksState();
	senetChanceState.num_ON_sticks = numOnSticks;

	// Probabilistic phase
	if (isChanceState) {
		double chanceStateValue = 0.0;
		for (int i = 0; i <= numOfSticks; i++) {
			senetChanceState.num_ON_sticks = i;
			curBoard.setChanceState(senetChanceState);

			double probability = choose(numOfSticks, i);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			chanceStateValue += probability * expectimax(curBoard, myColor,
					false, depth - 1, false, my_timer);

		}
		return (coefficientProbabilty * chanceStateValue);
	}

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 1;

	// only legal moves will be played
	nextLegalMoves = curBoard.getSuccessors(curColor);

	if (isFirst) {

		//if there is only an empty move
		if (nextLegalMoves[0].m_square == -1){
			selectedSquare = -1;
			throw 11;
		}
		else
			selectedSquare = nextLegalMoves[0].m_square;
	}

	//My turn
	if (myColor == curColor) {
		curMax = (double) INT_MIN;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			nextMove = nextLegalMoves[i];
			prepareUndo(nextMove, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			curBoard.makeMove(curColor, nextMove);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			value = expectimax(curBoard, myColor, true, depth - 1, false,
					my_timer);
			if (value > curMax) {
				curMax = value;
				//only the first recursion
				if (isFirst) {
					selectedSquare = nextMove.m_square;
				}
			}
			//			curMax = ((curMax > value) ? curMax : value);

			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);
		}
		return curMax;

	} else { // Opponent turn
		curMin = (double) INT_MAX;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			nextMove = nextLegalMoves[i];
			prepareUndo(nextMove, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			curBoard.makeMove(curColor, nextMove);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			value = expectimax(curBoard, myColor, true, depth - 1, false,
					my_timer);
			curMin = ((curMin < value) ? curMin : value);

			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);
		}
		return curMin;
	}

}

void Algorithem::prepareUndo(SenetMove & nextMove,
		int & posBefore,
		int & posAfter, int & numOnSticks, SmartSenetBoard & curBoard,
		bool & isPeaceOnReBirthPlace) {
	//nextMove = nextLegalMoves[i];
	posBefore = nextMove.m_square;
	// if there is no legal move or numOnStick 0, there is no need to do swap in undo
	if (posBefore == -1)
		return;

	//getSticks is ok, because i set it before, in the chance step
	posAfter = posBefore + numOnSticks;

	if (posAfter >= curBoard.GetNumOFSquaresBoard())
		return; // don't do next check

	// checking if there there a piece on posAfter in case posAfter is rebirth square
	if ((curBoard.getBoardState(posAfter)).square_type
			== SmartSenetBoard::REBIRTH_FROM) {
		// posAfter will be the position after the jump
		if ((curBoard.getBoardState(posAfter)).player_color
				!= Definitions::NONE) {
			isPeaceOnReBirthPlace = true;
		}
		posAfter = curBoard.findAvailableRebirthToSquare(posAfter);
	}

}

void Algorithem::undo(SmartSenetBoard & curBoard,
		SenetChanceState & senetChanceState, int & posAfter, int & posBefore,
		const Definitions::PlayerColor & curColor,
		bool & isPeaceOnReBirthPlace, int & numOnSticks) {
	// returns the previous chance in the board (number on sticks)
	curBoard.setChanceState(senetChanceState);
	// Sets curPlayer to to the current colloer which represent the curPlayer;
	curBoard.m_curPlayer = curColor;

	// if there is no legal move or numOnStick 0, there is no need to do swap in undo
	if (posBefore == -1)
		return;
	if (posAfter >= curBoard.GetNumOFSquaresBoard()) {
		// returns the piece that left the board back to its previous place.
		curBoard.setBoardState(posBefore, curColor);

	} else if ((curBoard.getBoardState(posBefore + numOnSticks)).square_type
			== SmartSenetBoard::REBIRTH_FROM) {

		if (posAfter != (posBefore + numOnSticks)) {
			if (isPeaceOnReBirthPlace) {
				curBoard.swap(posBefore, posBefore + numOnSticks);
				curBoard.swap(posAfter, posBefore);
			} else {
				curBoard.swap(posBefore, posAfter);
			}

		} else {
			curBoard.swap(posBefore, posAfter);
		}
	} else {
		curBoard.swap(posBefore, posAfter);
	}
	isPeaceOnReBirthPlace = false;
	//		if (posAfter != curBoard.findAvailableRebirthToSquare(posAfter)) {
	//			posAfter = curBoard.findAvailableRebirthToSquare(posAfter);
	//			if (isPeaceOnReBirthPlace) {
	//				curBoard.swap(posBefore, posBefore + numOnSticks);
	//				curBoard.swap(posAfter, posBefore);
	//			} else {
	//				curBoard.swap(posBefore, posAfter);
	//			}

}

int Algorithem::choose(int x, int y) {
	int score = 1;
	for (int i = x; i > y; i--)
		score *= i;
	score /= factorial(x - y);
	return score;
}

int Algorithem::factorial(int a) {
	if (a > 1)
		return (a * factorial(a - 1));
	else
		return (1);
}

double Algorithem::heuristic(SmartSenetBoard & curBoard,
		const Definitions::PlayerColor myColor) {

	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK) && (myColor
			== Definitions::BLACK))
		return curHeuristic->maxHeuristic;
	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE) && (myColor
			== Definitions::WHITE))
		return curHeuristic->maxHeuristic;
	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK) && (myColor
			== Definitions::WHITE))
		return curHeuristic->minHeuristic;
	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE) && (myColor
			== Definitions::BLACK))
		return curHeuristic->minHeuristic;

	double boardHeuristic = curHeuristic->getBoradHeuristic(curBoard, myColor);
	return (boardHeuristic);
}

int Algorithem::startStarOne(SmartSenetBoard& smartSenetBoard,
		GameTimer& my_timer, Heuristic* h) {

	curHeuristic = h;
	Definitions::PlayerColor playerColor = smartSenetBoard.getCurPlayerColor();
	numOfSticks = smartSenetBoard.m_num_sticks;
	coefficientProbabilty = pow(0.5, numOfSticks);

	//	setMaxMinHeuristics(smartSenetBoard);

	double initAlpah = curHeuristic->minHeuristic;
	double initBeta = curHeuristic->maxHeuristic;

	try {
		starOne(smartSenetBoard, playerColor, false, 5, true, my_timer,
				initAlpah, initBeta);
	} catch (int x) {
		if (x == 1) {
			//TODO remove this before submission
			counter++;
			printf(
					"*******************SHITTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtt I'm out of time***************************************************\n");
		}
	}

	// maybe return Move instead of int
	return selectedSquare;

}

int Algorithem::startIteritiveStarOne(SmartSenetBoard& smartSenetBoard,
		GameTimer& my_timer, Heuristic* h) {

	curHeuristic = h;
	Definitions::PlayerColor playerColor = smartSenetBoard.getCurPlayerColor();
	numOfSticks = smartSenetBoard.m_num_sticks;
	coefficientProbabilty = pow(0.5, numOfSticks);

	//	setMaxMinHeuristics(smartSenetBoard);

	double initAlpah = curHeuristic->minHeuristic;
	double initBeta = curHeuristic->maxHeuristic;
	double value = curHeuristic->minHeuristic;
	double tmpValue;
	int bestSquareForNextMove = -1;
	try {
		//int depth = curBestDepth;
		while(true){
			
			tmpValue = starOne(smartSenetBoard, playerColor, false, curBestDepth, true, my_timer,
				initAlpah, initBeta);
			flag = true;

			if (curBestDepth > 20){
				curBestDepth = 10;
				break;
			}

			curBestDepth++;
			if (tmpValue > value){
				value = tmpValue;
				bestSquareForNextMove = selectedSquare;	
			}
			//	depth++;
		//	curBestDepth = depth;
		}
	} catch (int x) {
		if (x == 1) {
			//TODO remove this before submission
			//counter++;
			//printf(
			//		"*******************SHITTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtt I'm out of time***************************************************\n");
		
		}
	}
	
	curBestDepth --;
	//cout << curBestDepth << endl; 
	/*if (flag == true)
		flag = false;
	else
		cout << " found one" << endl;*/ 
	
	if (bestSquareForNextMove == -1)
		bestSquareForNextMove = selectedSquare;

	// maybe return Move instead of int
	return bestSquareForNextMove;

}
double Algorithem::starOne(SmartSenetBoard& curBoard,
		const Definitions::PlayerColor myColor, bool isChanceState, int depth,
		bool isFirst, GameTimer& my_timer, double alpha, double beta) {

	vector<SenetMove> nextLegalMoves;
	SenetMove nextMove;
	double curMax, curMin, value;
	int posBefore, posAfter;
	Definitions::PlayerColor curColor;
	int numOnSticks;
	SenetChanceState senetChanceState;
	bool isPeaceOnReBirthPlace = false;

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 1;

	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK)
			|| (curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE)
			|| (depth == 0)) {
		return heuristic(curBoard, myColor); // should return heuristic here
	}

	curColor = curBoard.getCurPlayerColor();
	numOnSticks = curBoard.getSticksState();
	senetChanceState.num_ON_sticks = numOnSticks;

	// Probabilistic phase
	if (isChanceState) {
		double chanceStateValue = 0.0;
		double probability;
		double optimalChanceStateValue = 0.0;
		double optimalProbabilty = 0.0;
		double value = 0.0;

		for (int i = 0; i <= numOfSticks; i++) {
			optimalChanceStateValue = 0.0;
			senetChanceState.num_ON_sticks = i;
			curBoard.setChanceState(senetChanceState);

			probability = choose(numOfSticks, i);
			
			chanceStateValue += probability * starOne(curBoard, myColor, false,
					depth - 1, false, my_timer, alpha, beta);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;

			// if i'm under max state and above min state.
			if (myColor != curColor) {
				for (int j = i + 1; j <= numOfSticks; j++) {
					optimalProbabilty = choose(numOfSticks, j);
					optimalChanceStateValue += optimalProbabilty
							* curHeuristic->maxHeuristic;
					
				}

				optimalChanceStateValue = coefficientProbabilty
						* (chanceStateValue + optimalChanceStateValue);

				// I get alpha which is a maximal value from my fathers,
				// then if the optimal value i can in this point is lower then alpha
				// then there is no point to continue search the tree --> prune.
				if (optimalChanceStateValue <= alpha) {
					//					printf("optimal prune(alpha) %lf \n",
					//							optimalChanceStateValue);
					return optimalChanceStateValue;
				}
			}
			// if i'm under min state and above max state.
			else {
				for (int j = i + 1; j <= numOfSticks; j++) {
					optimalProbabilty = choose(numOfSticks, j);
					optimalChanceStateValue += optimalProbabilty
							* curHeuristic->minHeuristic;

					
				}

				optimalChanceStateValue = coefficientProbabilty
						* (chanceStateValue + optimalChanceStateValue);

				// I get beta which is a minimal value from my fathers,
				// then if the optimal value i can in this point is bigger then beta
				// then there is no point to continue search the tree --> prune.
				if ((optimalChanceStateValue >= beta)) {
					//					printf("optimal prune(beta) %lf \n",
					//							optimalChanceStateValue);
					return optimalChanceStateValue;
				}

			}

		}
		return (coefficientProbabilty * chanceStateValue);
	}

	

	// only legal moves will be played
	nextLegalMoves = curBoard.getSuccessors(curColor);

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 1;

	// reordering the nodes
	reorderingNodes(nextLegalMoves, curBoard, numOnSticks, myColor, curColor);

	if (isFirst) {

		//if there is only an empty move
		if (nextLegalMoves[0].m_square == -1){
			selectedSquare = -1;
			throw 11;
		}
		else
			selectedSquare = nextLegalMoves[0].m_square;
	}

	

	//My turn
	if (myColor == curColor) {
		curMax = (double) INT_MIN;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			nextMove = nextLegalMoves[i];
			prepareUndo(nextMove, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			//TODO remove this
			//printBorad(curBoard);


			curBoard.makeMove(curColor, nextMove);
			

			value = starOne(curBoard, myColor, true, depth - 1, false,
					my_timer, alpha, beta);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);

			//TODO remove this
			//printBorad(curBoard);

			if (value > curMax) {
				curMax = value;
				//only the first recursion
				if (isFirst)
					selectedSquare = nextMove.m_square;

			}
			
			if (curMax > alpha)
				alpha =  curMax;
			
			if (curMax >= beta) {
				//printf("max prune, cur max: %lf \n", curMax);
				break;
			}

		}
		return curMax;

	} else { // Opponent turn
		curMin = (double) INT_MAX;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			nextMove = nextLegalMoves[i];
			prepareUndo(nextMove, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			//TODO remove this
			//printBorad(curBoard);

			curBoard.makeMove(curColor, nextMove);
			
			value = starOne(curBoard, myColor, true, depth - 1, false,
					my_timer, alpha, beta);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;
			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);

			//TODO remove this
			//printBorad(curBoard);
			
			if (value < curMin)
				curMin = value;
			
			if (curMin < beta)
				beta = curMin;

			if (curMin <= alpha) {
				//				printf("min prune, cur min: %lf \n", curMin);
				break;
			}
		}
		return curMin;
	}

}



typedef struct {
	double heuristic;
	SenetMove sm;
} proxy;

bool cmpMaxFun(proxy pLeft, proxy pRight) {
	return pLeft.heuristic > pRight.heuristic;
}

bool cmpMinFun(proxy pLeft, proxy pRight) {
	return pLeft.heuristic < pRight.heuristic;
}
void Algorithem::reorderingNodes(vector<SenetMove>& nextLegalMoves,
		SmartSenetBoard& smartSenetBoard, int numOnSticks,
		const Definitions::PlayerColor myColor,
		const Definitions::PlayerColor curColor) {

	int size = nextLegalMoves.size();
	// if i have only one move no need to reorder the nextLegalMoves
	// and if there is no move to take return;
	if (size < 2)
		return;

	int it = 0;
	list<proxy> reorderMoves;
	proxy node;
	SenetMove nextMove;
	int posBefore;
	int posAfter;
	bool isPeaceOnReBirthPlace = false;
	SenetChanceState senetChanceState;
	//	reorderMoves.resize(size);
	senetChanceState.num_ON_sticks = numOnSticks;

	//TODO to delete
	vector<string> players_names;

	for (it = 0; it < size; ++it) {

		//nextMove = nextLegalMoves[it].m_square;

		//TODO remove this
		//printBorad(smartSenetBoard);
		nextMove = nextLegalMoves[it];
		prepareUndo(nextMove, posBefore, posAfter,
				numOnSticks, smartSenetBoard, isPeaceOnReBirthPlace);
		smartSenetBoard.makeMove(curColor, nextMove);
		node.heuristic = heuristic(smartSenetBoard, myColor);
		node.sm = nextLegalMoves[it];
		reorderMoves.push_back(node);
		undo(smartSenetBoard, senetChanceState, posAfter, posBefore, curColor,
				isPeaceOnReBirthPlace, numOnSticks);

		//TODO remove this
		//printBorad(smartSenetBoard);

	}

	// if the current state is max state, the we want high to low list(highest
	//in the beggining),
	// else we are in min state - low to high (smallest in the beggining)
	if (myColor == curColor)
		reorderMoves.sort(cmpMaxFun);
	else
		reorderMoves.sort(cmpMinFun);
	list<proxy>::iterator cur;
	int i = 0;
	for (cur = reorderMoves.begin(); cur != reorderMoves.end(); cur++) {
		nextLegalMoves[i] = (*cur).sm;
//		printf("%d heuristic is: %lf\n", (*cur).sm.m_square, (*cur).heuristic);
		i++;
	}

//	for (int i = 0; i < nextLegalMoves.size(); i++)
//		printf("%d\n", nextLegalMoves[i].m_square);

}

SenetMove& Algorithem::getBestMove(vector<SenetMove>& nextLegalMoves,
		SmartSenetBoard& curBoard, int numOnSticks,
		const Definitions::PlayerColor myColor,
		const Definitions::PlayerColor curColor){

	int size = nextLegalMoves.size();
	// if i have only one move no need to reorder the nextLegalMoves
	// and if there is no move to take return;
	if (size == 1)
		return nextLegalMoves[0];
	
	int posOfBestHeuristic = 0;	
	SenetMove nextMove;
	int posBefore;
	int posAfter;
	bool isPeaceOnReBirthPlace = false;
	SenetChanceState senetChanceState;
	//	reorderMoves.resize(size);

	double tmpHeuristic = 0.0;
	double bestHeuristic;
	
	bestHeuristic = ((myColor == curColor) ? curHeuristic->minHeuristic : curHeuristic->maxHeuristic);

	senetChanceState.num_ON_sticks = numOnSticks;

	for (int i = 0; i < size; ++i) {

		//nextMove = nextLegalMoves[it].m_square;

		//TODO remove this
		//printBorad(curBoard);
		nextMove = nextLegalMoves[i];
		prepareUndo(nextMove, posBefore, posAfter,
				numOnSticks, curBoard, isPeaceOnReBirthPlace);
		curBoard.makeMove(curColor, nextMove);
		tmpHeuristic = heuristic(curBoard, myColor);
		
		//if max state
		if (myColor == curColor){
			if (tmpHeuristic > bestHeuristic){
				bestHeuristic = tmpHeuristic;
				posOfBestHeuristic = i;
			}

		}
		else{
			if (tmpHeuristic < bestHeuristic){
				bestHeuristic = tmpHeuristic;
				posOfBestHeuristic = i;
			}
		}

		undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
				isPeaceOnReBirthPlace, numOnSticks);

		//TODO remove this
		//printBorad(curBoard);

	}
	
	return nextLegalMoves[posOfBestHeuristic];

//	for (int i = 0; i < nextLegalMoves.size(); i++)
//		printf("%d\n", nextLegalMoves[i].m_square);

}

void Algorithem::printBorad(SmartSenetBoard& board){

	vector<string> players_names;
	if (board.getCurPlayerColor() == Definitions::WHITE) {
		players_names.push_back("Tutankhamun");
		players_names.push_back("OPPONENT");
	} else {
		players_names.push_back("OPPONENT");
		players_names.push_back("Nefertiti");
	}

	board.drawBoard(players_names);
					
	
}



double Algorithem::starTwo(SmartSenetBoard& curBoard,
		const Definitions::PlayerColor myColor, bool isChanceState, int depth,
		bool isFirst, GameTimer& my_timer, double alpha, double beta) {

	vector<SenetMove> nextLegalMoves;
	SenetMove nextMove;
	double curMax, curMin, value;
	int posBefore, posAfter;
	Definitions::PlayerColor curColor;
	int numOnSticks;
	SenetChanceState senetChanceState;
	bool isPeaceOnReBirthPlace = false;

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
					throw 1;

	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK)
			|| (curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE)
			|| (depth == 0)) {
				return heuristic(curBoard, myColor); // should return heuristic here
	}

	curColor = curBoard.getCurPlayerColor();
	numOnSticks = curBoard.getSticksState();
	senetChanceState.num_ON_sticks = numOnSticks;

	// Probabilistic phase
	if (isChanceState) {
		double chanceStateValue = 0.0;
		double probability;
		double optimalChanceStateValue = 0.0;
		double optimalProbabilty = 0.0;
		double value = 0.0;

		double* starTwoSticksBounds = new double[numOfSticks + 1];
		for (int i = 0; i <= numOfSticks; i++){
			senetChanceState.num_ON_sticks = i;
			curBoard.setChanceState(senetChanceState);
			starTwoSticksBounds[i] = getStarTwoBound(curBoard, myColor, false,
					depth - 1, false, my_timer, alpha, beta);	
			
		}

		if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 2;

		for (int i = 0; i <= numOfSticks; i++) {
			optimalChanceStateValue = 0.0;

			// if i'm under max state and above min state.
			if (myColor != curColor) {
				for (int j = i; j <= numOfSticks; j++) {
					optimalProbabilty = choose(numOfSticks, j);
					optimalChanceStateValue += optimalProbabilty * starTwoSticksBounds[j];
				}

				optimalChanceStateValue = coefficientProbabilty
						* (chanceStateValue + optimalChanceStateValue);

				// I get alpha which is a maximal value from my fathers,
				// then if the optimal value i can in this point is lower then alpha
				// then there is no point to continue search the tree --> prune.
				if (optimalChanceStateValue <= alpha) {
					//					printf("optimal prune(alpha) %lf \n",
					//							optimalChanceStateValue);
					return optimalChanceStateValue;
				}
			}
			// if i'm under min state and above max state.
			else {
				for (int j = i; j <= numOfSticks; j++) {
					optimalProbabilty = choose(numOfSticks, j);
					
					//printBorad(tempBoard);
					optimalChanceStateValue += optimalProbabilty * starTwoSticksBounds[j];
					
				}
				optimalChanceStateValue = coefficientProbabilty
						* (chanceStateValue + optimalChanceStateValue);

				// I get beta which is a minimal value from my fathers,
				// then if the optimal value i can in this point is bigger then beta
				// then there is no point to continue search the tree --> prune.
				if ((optimalChanceStateValue >= beta)) {
					//					printf("optimal prune(beta) %lf \n",
					//							optimalChanceStateValue);
					return optimalChanceStateValue;
				}

			}

			
			senetChanceState.num_ON_sticks = i;
			curBoard.setChanceState(senetChanceState);

			probability = choose(numOfSticks, i);
			/*if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 1;*/
			chanceStateValue += probability * starTwo(curBoard, myColor, false,
					depth - 1, false, my_timer, alpha, beta);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 3;
		}
		delete [] starTwoSticksBounds;
		starTwoSticksBounds = NULL;
		return (coefficientProbabilty * chanceStateValue);
	}

	// only legal moves will be played
	nextLegalMoves = curBoard.getSuccessors(curColor);

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 4;

	// reordering the nodes
	reorderingNodes(nextLegalMoves, curBoard, numOnSticks, myColor, curColor);

	if (isFirst) {

		//if there is only an empty move
		if (nextLegalMoves[0].m_square == -1){
			selectedSquare = -1;
			// The First move has no sons, no need to continue search on the tree.
			throw 11;
		}
		else
			selectedSquare = nextLegalMoves[0].m_square;
	}

	

	//My turn
	if (myColor == curColor) {
		curMax = (double) INT_MIN;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			nextMove = nextLegalMoves[i];
			prepareUndo(nextMove, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			//TODO remove this
			//SmartSenetBoard copiedBoard = curBoard;
			
			curBoard.makeMove(curColor, nextMove);

			value = starTwo(curBoard, myColor, true, depth - 1, false,
					my_timer, alpha, beta);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 5;
			//printBorad(curBoard);
			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);
			
		
			//TODO remove this
			//if (counter > 30){
			//cout << nextMove.m_square << endl;;
			//printBorad(copiedBoard);
			//printBorad(curBoard);
			//}

			if (value > curMax) {
				curMax = value;
				//only the first recursion
				if (isFirst)
					selectedSquare = nextMove.m_square;

			}
			
			if (curMax > alpha)
				alpha =  curMax;
			
			if (curMax >= beta) {
				//printf("max prune, cur max: %lf \n", curMax);
				break;
			}

		}
		return curMax;

	} else { // Opponent turn
		curMin = (double) INT_MAX;
		for (int i = 0; i < (int) (nextLegalMoves.size()); i++) {
			nextMove = nextLegalMoves[i];
			prepareUndo(nextMove, posBefore, posAfter,
					numOnSticks, curBoard, isPeaceOnReBirthPlace);

			//TODO remove this
			//printBorad(curBoard);

			curBoard.makeMove(curColor, nextMove);
			value = starTwo(curBoard, myColor, true, depth - 1, false,
					my_timer, alpha, beta);
			if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
				throw 6;
			undo(curBoard, senetChanceState, posAfter, posBefore, curColor,
					isPeaceOnReBirthPlace, numOnSticks);

			//TODO remove this
			//printBorad(curBoard);
			
			if (value < curMin)
				curMin = value;
			
			if (curMin < beta)
				beta = curMin;

			if (curMin <= alpha) {
				//				printf("min prune, cur min: %lf \n", curMin);
				break;
			}
		}
		return curMin;
	}

}


double Algorithem::getStarTwoBound(SmartSenetBoard& curBoard,
		const Definitions::PlayerColor myColor, bool isChanceState, int depth,
		bool isFirst, GameTimer& my_timer, double alpha, double beta){

	Definitions::PlayerColor curColor = curBoard.getCurPlayerColor();
	vector<SenetMove> nextLegalMoves;
	double value = 0.0;
	int posBefore, posAfter;
	bool isPeaceOnReBirthPlace = false;
	SenetChanceState senetChanceState;
	int numOnSticks = curBoard.getSticksState();
	senetChanceState.num_ON_sticks = numOnSticks;

	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
					throw 8;
	if ((curBoard.getBoardResult() == SmartSenetBoard::WIN_BLACK)
			|| (curBoard.getBoardResult() == SmartSenetBoard::WIN_WHITE)
			|| (depth == 0)) {
				return heuristic(curBoard, myColor); 
	}

	nextLegalMoves  = curBoard.getSuccessors(curColor);
	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 9;
	SenetMove move = getBestMove(nextLegalMoves, curBoard, curBoard.getSticksState(),myColor,curColor);
	prepareUndo(move, posBefore, posAfter,numOnSticks, curBoard,isPeaceOnReBirthPlace);

	curBoard.makeMove(curColor, move);
	value = starTwo(curBoard, myColor,true, depth - 1,isFirst, my_timer,alpha, beta);
	if (my_timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
		throw 10;
	undo(curBoard,senetChanceState,posAfter,posBefore,curColor,isPeaceOnReBirthPlace,numOnSticks);
	
	return value;
}







int Algorithem::startStarTwo(SmartSenetBoard& smartSenetBoard,
		GameTimer& my_timer, Heuristic* h) {

	curHeuristic = h;
	Definitions::PlayerColor playerColor = smartSenetBoard.getCurPlayerColor();
	numOfSticks = smartSenetBoard.m_num_sticks;
	coefficientProbabilty = pow(0.5, numOfSticks);

	//	setMaxMinHeuristics(smartSenetBoard);

	double initAlpah = curHeuristic->minHeuristic;
	double initBeta = curHeuristic->maxHeuristic;

	try {
		starTwo(smartSenetBoard, playerColor, false, 6, true, my_timer,
				initAlpah, initBeta);
	} catch (int x) {
		if (x == 1) {
			//TODO remove this before submission
			//counter++;
			//printf(
			//		"*******************SHITTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtt I'm out of time***************************************************\n");
		}
	}

	// maybe return Move instead of int
	return selectedSquare;

}

int Algorithem::startIteritiveStarTwo(SmartSenetBoard& smartSenetBoard,
		GameTimer& my_timer, Heuristic* h) {

	curHeuristic = h;
	Definitions::PlayerColor playerColor = smartSenetBoard.getCurPlayerColor();
	numOfSticks = smartSenetBoard.m_num_sticks;
	coefficientProbabilty = pow(0.5, numOfSticks);

	//	setMaxMinHeuristics(smartSenetBoard);

	double initAlpah = curHeuristic->minHeuristic;
	double initBeta = curHeuristic->maxHeuristic;
	double value = curHeuristic->minHeuristic;
	double tmpValue;
	int bestSquareForNextMove = -1;
	try {
		//int depth = curBestDepth;
		while(true){
			counterIteritive++;
			tmpValue = starTwo(smartSenetBoard, playerColor, false, curBestDepth, true, my_timer,
				initAlpah, initBeta);
			
			flag = true;

			if (curBestDepth > 13){
				curBestDepth = 10;
				break;
			}

			curBestDepth++;
			if (tmpValue > value){
				value = tmpValue;
				bestSquareForNextMove = selectedSquare;	
			}
			//	depth++;
		//	curBestDepth = depth;
		}
	} catch (int x) {
		if (x > 0) {
			curException = x;
			//TODO remove this before submission
			//counter++;
			//printf(
			//		"*******************SHITTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtt I'm out of time***************************************************\n");
		
		}
	}
	
	curBestDepth--;
	//cout << curBestDepth << endl; 
	//if (flag == true)
	//	flag = false;
	//else
	//	counter++;
	//	//cout << " found one" << endl; 

	//// maybe return Move instead of int
	if (bestSquareForNextMove == -1)
		bestSquareForNextMove = selectedSquare;
	return bestSquareForNextMove;

}
